package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 组合总和 III
 * <p>
 * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 * <p>
 * 只使用数字1到9
 * 每个数字 最多使用一次
 * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 * @date 2025/6/12 17:56
 */
public class CombinationSum3_216 {

    public static void main(String[] args) {
        CombinationSum3_216 combinationSum3216 = new CombinationSum3_216();

        int k = 3, n = 7;
        List<List<Integer>> lists = combinationSum3216.combinationSum3(k, n);
        lists.forEach(System.out::println);
    }

    /**
     * dmsxl-回溯
     * <p>
     * 分析：
     * 1.树的深度由 k 决定，因为题目要求找 k 个数。
     * 2.由题目可知，目标元素在[1, n]之间，是不重复的，并且每个元素只能用一次
     */
    List<List<Integer>> result2 = new ArrayList<>();

    List<Integer> path2 = new ArrayList<>();

    public List<List<Integer>> combinationSum32(int k, int n) {
        backTracking2(n, k, 1, 0);
        return result2;
    }

    private void backTracking2(int targetSum, int k, int startIndex, int sum) {
        // 个数满足，且元素和满足，才记录
        if (path2.size() == k) {
            if (sum == targetSum) result2.add(new ArrayList<>(path2));
            return;
        }

        for (int i = startIndex; i <= 9; i++) {
            // 记录元素，以及path2的元素和
            path2.add(i);
            sum += i;

            backTracking2(targetSum, k, i + 1, sum);

            //回溯
            path2.remove(path2.size() - 1);
            //回溯
            sum -= i;
        }
    }

    /**
     * 个解-回溯
     */
    List<List<Integer>> ans = new ArrayList<>();

    List<Integer> group = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1);

        return ans;
    }

    public void backTracking(int k, int n, int startNum) {
        if (k == 0) {
            // 个数、和都满足，则记录
            if (n == 0) ans.add(new ArrayList<>(group));

            // 个数满足，但和不满足，则直接返回
            return;
        }

        // 遍历处理每一个元素
        for (int i = startNum; i <= 9; i++) {
            group.add(i);

            // 递归找下一个元素
            // k-1，表示目标组合还差的元素个数
            // n-i，是因为这里表示group已有元素之和与目标 n 的差距；当扣减为0时，表示找到元素和=n的组合
            backTracking(k - 1, n - i, i + 1);

            // 移除末尾元素
            group.remove(group.size() - 1);
        }
    }

}
